Multi-label classification is becoming increasingly ubiquitous, but not much attention has been paid to interpretability. In this paper, we develop a multi-label classifier that can be represented as a concise set of simple "if-then" rules, and thus, it offers better interpretability compared to black-box models. Notably, our method is able to find a small set of relevant patterns that lead to accurate multi-label classification, while existing rule-based classifiers are myopic and wasteful in searching rules,requiring a large number of rules to achieve high accuracy. In particular, we formulate the problem of choosing multi-label rules to maximize a target function, which considers not only discrimination ability with respect to labels, but also diversity. Accounting for diversity helps to avoid redundancy, and thus, to control the number of rules in the solution set. To tackle the said maximization problem we propose a 2-approximation algorithm, which relies on a novel technique to sample high-quality rules. In addition to our theoretical analysis, we provide a thorough experimental evaluation, which indicates that our approach offers a trade-off between predictive performance and interpretability that is unmatched in previous work.

决策树是流行的分类模型，提供了很高的准确性和直观的解释。但是，随着树大小的生长，模型的解释性会恶化。传统的树木诱导算法（例如C4.5和推车）依赖于减少杂质的功能，这些功能可以促进每次分裂的判别能力。因此，尽管这些传统方法在实践中是准确的，但没有理论上保证它们会生产小树。在本文中，我们通过证明简单的增强能够为它们提供复杂性保证的情况，证明使用了普通杂质功能的普通家族，包括熵和Gini Index的流行功能。我们考虑一个通用设置，其中要分类的对象是从任意概率分布中绘制的，分类可以是二进制或多类，并且分裂测试与非均匀成本相关联。作为树木复杂性的衡量标准，我们采用了预期的成本来分类从输入分布中得出的对象，在统一成本的情况下，该对象是预期的测试数量。我们提出了一种树诱导算法，该算法在树复杂性上提供对数近似保证。在温和的假设下，该近似因素紧密到恒定因子。该算法递归选择了一个测试，该测试最大化贪婪的标准定义为三个组件的加权总和。前两个组件鼓励选择分别提高树木平衡和成本效益的测试，而第三个杂质减少组件则鼓励选择更具判别性的测试。如我们的经验评估所示，与原始的启发式方法相比，增强算法在预测准确性和树木复杂性之间取得了良好的平衡。

在涉及矩阵计算的问题中，杠杆的概念发现了大量应用。特别是，将矩阵的列与其领先的单数矢量跨越的子空间相关联的杠杆分数有助于揭示列亚集，以大约将矩阵分配给具有质量保证的矩阵。因此，它们为各种机器学习方法提供了坚实的基础。在本文中，我们扩展了杠杆分数的定义，以将矩阵的列与单数矢量的任意子集相关联。我们通过将杠杆分数和子空间之间的主要角度的概念联系起来，在列和奇异矢量子集之间建立精确的联系。我们采用此结果来设计近似算法，并为两个众所周知的问题提供可证明的保证：广义列子集选择和稀疏的规范相关分析。我们运行数值实验，以进一步了解所提出的方法。我们得出的新颖界限提高了我们对矩阵近似中基本概念的理解。此外，我们的见解可能是进一步贡献的基础。

本次调查绘制了用于分析社交媒体数据的生成方法的研究状态的广泛的全景照片（Sota）。它填补了空白，因为现有的调查文章在其范围内或被约会。我们包括两个重要方面，目前正在挖掘和建模社交媒体的重要性：动态和网络。社会动态对于了解影响影响或疾病的传播，友谊的形成，友谊的形成等，另一方面，可以捕获各种复杂关系，提供额外的洞察力和识别否则将不会被注意的重要模式。